﻿// 4575. Bi数和Phi数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>



using namespace std;
/*
https://www.acwing.com/problem/content/4578/

给定一个正整数 x，ϕ(x)表示小于 x 且与 x 互质的正整数的数量。

例如，ϕ(9)=6，因为 1,2,4,5,7,8与 9互质。

现在，给定一个长度为 n 的正整数序列 a1,a2,…,an
，请你构造一个长度为 n 的正整数序列 b1,b2,…,bn，要求：

对于 1≤i≤n，ϕ(bi)≥ai始终成立。
设 sum=b1+b2+…+bn，sum 的值应尽可能小。
请你计算并输出 sum 的最小可能值。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式 
每组数据输出一行结果，格式为 Case i: x Xukha，其中 i
 为组别编号（从 1 开始），x 为 sum 的最小可能值。

数据范围
1≤T≤100
,
1≤n≤10000
,
1≤ai≤10^6
。

输入样例：
3
5
1 2 3 4 5
6
10 11 12 13 14 15
2
1 1
输出样例：
Case 1: 22 Xukha
Case 2: 88 Xukha
Case 3: 4 Xukha
*/

const int N = 1000100;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int T, n;
int a[10010];


void solve(int idx) {
    cin >> n;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int l = 0; int r = cnt - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (primes[mid] - 1 >= a[i]) r = mid;
            else l = mid + 1;
        }

        ans += primes[l];
    }
    //cout << ans << endl;
    printf("Case %d: %lld Xukha\n",idx,ans);
}


int main()
{
    get_primes(1000100);
    //cout << primes[cnt - 1] << endl;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }

	return 0;
}

 